import java.util.Deque;

class Solution {
    // 双指针
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (k <= 1)
            return nums;
        int[] res = new int[len - k + 1];

        for (int i = 0; i < res.length; i++) {
            int left = i;
            int right = left + k - 1;
            int tmp = nums[left];
            for (int j = left; j <= right; j++) {
                if (tmp < nums[j]) {
                    tmp = nums[j];
                }
            }
            res[i] = tmp;
        }
        return res;
    }

    // 单调队列
    /*
     * （头，尾，尾，头）
     * 第一步，头部出队，清理超范围
     * 第二步，篮球队清理，移除尾部，在当前值前面的还小于当前值的元素
     * 第三步，尾部入队，尾部范围正确
     * 第四步，返回头部-一当前窗口最大值
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        if (k <= 1)
            return nums;
        Deque<Integer> dq = new ArrayDeque<>();
        int[] res = new int[n - k + 1];
        int index = 0;
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && i - dq.peek() + 1 > k) {
                dq.poll();
            }

            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }

            dq.offer(i); // 放第一个

            if (i >= k - 1) {
                res[index] = nums[dq.peek()];
                index++;
            }
        }
        return res;
    }
}